package top.interview

import problem.Problem

class Q169MajorityElement extends Problem {

  def majorityElement(nums: Array[Int]): Int = {
    val sorted = nums.sorted
    var i = 1
    var last = sorted.head
    var len = 1
    val n = if (sorted.length % 2 == 0) sorted.length / 2 else sorted.length / 2 + 1
    while (i < sorted.length && len < n) {
      if (sorted(i) == last) len += 1
      else len = 1
      last = sorted(i)
      i += 1
    }
    last
  }

  def majorityElement2(nums: Array[Int]): Int = {
    val (n, count) = nums.tail.foldLeft((nums.head, 1)) {
      case ((mode, count), i) =>
        if (count == 0) (i, 1)
        else if (i == mode) (mode, count + 1)
        else (mode, count - 1)
    }
    n
  }

  override def test(): Unit = {
    majorityElement(Array(3)) shouldBe 3
    majorityElement(Array(3, 2, 3)) shouldBe 3
    majorityElement(Array(2, 2, 1, 1, 1, 2, 2)) shouldBe 2

    majorityElement2(Array(3)) shouldBe 3
    majorityElement2(Array(3, 2, 3)) shouldBe 3
    majorityElement2(Array(2, 2, 1, 1, 1, 2, 2)) shouldBe 2
  }
}
